#ifndef HASHTABLE_H
#define HASHTABLE_H

#include "lib.h"

#include <string.h>
#include <wchar.h>
#include <malloc.h>

namespace Library
{

template<typename V> class HashTableIterator;

/**
 * @class HashTable
 * A template class which stores unsorted key/value pairs.
 */
template<typename V> class HashTable
{
	friend class HashTableIterator<V>;

	public:
		enum { TABLE_SIZE = 100 };

		HashTable(uint32 tableSize = TABLE_SIZE);
		~HashTable();

		bool8	add(const String& key, V value);
		bool8	get(const String& key, V* value);
		bool8	remove(const String& key);
		bool8	rename(const String& from, const String& to);
		void	clear();
		uint32	size();
		void	vaporize();

	protected:
		class Entry
		{
			friend class HashTable<V>;
			friend class HashTableIterator<V>;

			public:
				Entry(uint32 id, const String& key, V value)
					{
						m_id	= id;
						m_value	= value;
						m_prev	= 0;
						m_next	= 0;
						m_key	= key;
					};

				~Entry()
					{
					};

			protected:
				uint32		m_id;
				String		m_key;
				V			m_value;
				Entry *		m_prev;
				Entry *		m_next;

			// prohibited
			private:
				Entry();	
				Entry(Entry &);
				Entry & operator=(Entry);
		};

		Entry *		find(const String& key);
		bool8		insert(Entry * entry);
		Entry *		extract(const String& key);
		uint32		hash(const String& key);

	private:
		Entry **	m_table;
		uint32		m_tableSize;
		uint32		m_count;

	// prohibited
	private:
		HashTable(HashTable &);
		HashTable & operator=(HashTable &);
};

/**
 * A template class iterator for HashTable.
 */
template<typename V> class HashTableIterator
{
	public:
		HashTableIterator(HashTable<V> * table);
		~HashTableIterator();

		const String*	key();
		V				value();

		bool8	begin();
		bool8	end();

		bool8	operator++(int);
		bool8	operator--(int);

	protected:
		bool8	beginOn(uint32 on);
		bool8	endOn(uint32 on);

	private:
		HashTable<V> *			m_table;
		uint32					m_index;
		typename HashTable<V>::Entry * 	m_curr;
		typename HashTable<V>::Entry * 	m_prev;
		typename HashTable<V>::Entry * 	m_next;

	// prohibited
	private:
		HashTableIterator(HashTableIterator &);
		HashTableIterator & operator=(HashTableIterator &);
};


//----------------------------------------------------------------------------
// HashTable
//
template<class V>
HashTable<V>::HashTable(uint32 tableSize)
{
	uint32	index;

	m_count		= 0;
	m_tableSize	= tableSize < 5 ? 5 : tableSize;
	m_table		= new Entry * [ m_tableSize ];
	if (m_table)
	{
		for (index = 0; index < m_tableSize; index++)
			m_table[index] = 0;
	}
}

template<class V>
HashTable<V>::~HashTable(void)
{
	clear();
	delete [] m_table;
}

template<class V> bool8
HashTable<V>::add(const String& key, V value)
{
	Entry *	entry;
	uint32	id;
	uint32	index;

	if (key.isEmpty() || find(key))
		return false;

	id		= hash(key);
	index	= id % m_tableSize;
	entry	= new Entry(id, key, value);
	if (entry)
		return insert(entry);

	return false;
}

template<class V> bool8
HashTable<V>::get(const String& key, V* value)
{
	Entry * entry;

	if (!key.isEmpty()  &&  (entry = find(key)) != NULL)
	{
		*value = entry->m_value;
		return true;
	}

	return false;
}

template<class V> bool8
HashTable<V>::remove(const String& key)
{
	Entry * entry;

	if (key.isEmpty()  ||  (entry = extract(key)) == NULL)
		return false;

	delete entry;

	return true;
}

template<class V> bool8
HashTable<V>::rename(const String& from, const String& to)
{
	Entry * entry_from;
	Entry * entry_to;
	uint32	id;
	uint32	index;

	if (from.IsEmpty() || to.IsEmpty() || find(to) || !(entry_from = find(from)))
		return false;

	id		= hash(to);
	index	= id % m_tableSize;
	entry_to= new Entry(id, to, entry_from->m_value);

	if (entry_to)
	{
		if (insert(entry_to))
			return remove(from);
		else
			delete entry_to;
	}

	return false;
}

template<class V> void
HashTable<V>::clear()
{
	Entry *	entry;
	Entry *	next;
	uint32	index;

	for (index = 0; index < m_tableSize; index++)
	{
		entry = m_table[index];
		m_table[index] = 0;

		while (entry)
		{
			next = entry->m_next;
			delete entry;
			entry = next;
		}
	}

	m_count = 0;
}

template<class V> void
HashTable<V>::vaporize()
{
	Entry *	entry;
	uint32	index;

	for (index = 0; index < m_tableSize; index++)
	{
		for (entry = m_table[index]; entry; entry = entry->m_next)
		{
			delete entry->m_value;
			entry->m_value = 0;
		}
	}

	// Yes we walk the list twice, but it's better than duplicating code.
	clear();
}

template<class V> inline uint32
HashTable<V>::size()
{
	return m_count;
}

template<class V> typename HashTable<V>::Entry *
HashTable<V>::find(const String& key)
{
	Entry * entry;
	uint32	id;
	uint32	index;

	if (key.isEmpty())
		return 0;

	id		= hash(key);
	index	= id % m_tableSize;
	entry	= m_table[index];

	while (entry)
	{
		if (entry->m_id == id && entry->m_key.caseCompare(key) == 0)
			break;

		entry = entry->m_next;
	}
	
	return entry;
}

template<class V> bool8
HashTable<V>::insert(Entry * entry)
{
	uint32 index = entry->m_id % m_tableSize;

	if (m_table[index])
		m_table[index]->m_prev = entry;

	entry->m_next = m_table[index];
	m_table[index] = entry;

	m_count++;

	return true;
}

template<class V> typename HashTable<V>::Entry *
HashTable<V>::extract(const String& key)
{
	Entry * entry;
	Entry * prev;
	Entry * next;

	entry = find(key);
	if (!entry)
		return 0;

	prev = entry->m_prev;
	next = entry->m_next;

	if (prev)
		prev->m_next = next;
	else
		m_table[ entry->m_id % m_tableSize ] = next;

	if (next)
		next->m_prev = prev;

	m_count--;

	return entry;
}

template<class V> uint32
HashTable<V>::hash(const String& key)
{
	uint32	hash = 0;
	uint32	nibble;
	uint32	len = 0;

	len = key.getLength();

	for( uint32 i = 0; i < len; i++ )
	{
		hash = (hash << 4) + towlower(key[i]);
		if ((nibble = (hash & 0xf0000000)) != 0)
		{
			hash ^= nibble >> 24;
			hash &= ~nibble;
		}
	}

	return hash;
}

template<class V> inline
HashTableIterator<V>::HashTableIterator(HashTable<V> * table)
{
	m_table	= table;
	m_index	= 0;
	m_curr	= 0;
	m_prev	= 0;
	m_next	= 0;
}

template<class V> inline
HashTableIterator<V>::~HashTableIterator()
{
}

template<class V> inline const String*
HashTableIterator<V>::key()
{
	if (m_curr)
		return &m_curr->m_key;

	return 0;
}

template<class V> inline V
HashTableIterator<V>::value()
{
	if (m_curr)
		return m_curr->m_value;

	return 0;
}

template<class V> bool8
HashTableIterator<V>::begin()
{
	m_index	= 0;
	m_curr	= 0;
	m_prev	= 0;
	m_next	= 0;

	if (!beginOn(m_index))
		return operator++(0);

	return true;
}

template<class V> bool8
HashTableIterator<V>::end()
{
	m_index = m_table->m_tableSize - 1;
	m_curr	= 0;
	m_prev	= 0;
	m_next	= 0;

	if (!endOn(m_index))
		return operator--(0);

	return true;
}

template<class V> bool8
HashTableIterator<V>::operator++(int)
{
	// NOTE: It's highly probable 'm_curr' was deleted.  Do not trust its
	//       contents to update 'm_prev' and 'm_next' pointers.
	m_curr = m_next;
	if (m_curr)
	{
		m_prev = m_curr->m_prev;
		m_next = m_curr->m_next;
		return true;
	}

	for (m_index++ ; m_index < m_table->m_tableSize; m_index++)
	{
		if (beginOn(m_index))
			return true;
	}

	return false;
}

template<class V> bool8
HashTableIterator<V>::operator--(int)
{
	// NOTE: It's highly probable 'curr' was deleted.  Do not trust its
	//       contents to update 'prev' and 'next' pointers.
	m_curr = m_prev;
	if (m_curr)
	{
		m_prev = m_curr->m_prev;
		m_next = m_curr->m_next;
		return true;
	}

	for (m_index--; m_index >= 0; m_index--)
	{
		if (endOn(m_index))
			return true;
	}

	return false;
}

template<class V> bool8
HashTableIterator<V>::beginOn(uint32 on)
{
	if (m_table->m_table[on] == 0)
		return false;

	m_curr = m_table->m_table[on];
	m_prev = m_curr->m_prev;
	m_next = m_curr->m_next;

	return true;
}

template<class V> bool8
HashTableIterator<V>::endOn(uint32 on)
{
	HashTable<V>::Entry *	last;
	HashTable<V>::Entry *	ptr;

	if (m_table->m_table[on] == 0)
		return false;

	last = ptr = m_table->m_table[on];
	while (ptr)
	{
		last = ptr;
		ptr = ptr->m_next;
	}

	m_prev = last->m_prev;
	m_curr = last;
	m_next = last->m_next;

	return true;
}

}; // namespace Library

#endif
